#
# @lc app=leetcode.cn id=12 lang=python3
#
# [12] 整数转罗马数字
#
# https://leetcode-cn.com/problems/integer-to-roman/description/
#
# algorithms
# Medium (59.25%)
# Total Accepted:    27K
# Total Submissions: 45.4K
# Testcase Example:  '3'
#
# 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
# 
# 字符          数值
# I             1
# V             5
# X             10
# L             50
# C             100
# D             500
# M             1000
# 
# 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V +
# II 。
# 
# 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5
# 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
# 
# 
# I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
# X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
# C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
# 
# 
# 给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
# 
# 示例 1:
# 
# 输入: 3
# 输出: "III"
# 
# 示例 2:
# 
# 输入: 4
# 输出: "IV"
# 
# 示例 3:
# 
# 输入: 9
# 输出: "IX"
# 
# 示例 4:
# 
# 输入: 58
# 输出: "LVIII"
# 解释: L = 50, V = 5, III = 3.
# 
# 
# 示例 5:
# 
# 输入: 1994
# 输出: "MCMXCIV"
# 解释: M = 1000, CM = 900, XC = 90, IV = 4.
# 
#
import pdb 
# class Solution:
#     def intToRoman(self, num: int) -> str:
#         if num < 0 or num > 3999:
#             return None
#         # pdb.set_trace()
#         dct = {1:'I', 2:'II', 3:'III', 4:'IV', 5:'V', 6:'VI', 7:'VII', 8:'VIII', 9 \
#                :'IX', 10:'X', 40:'XL', 50:'L', 90:'XC', 100:'C', 400:'CD',500:'D', 900:'CM', 1000:'M'}
#         dig_level = 0
#         tmp = num
#         while tmp >= 10:
#             dig_level += 1
#             tmp //= 10
#         tmp = num
#         result = ''
#         while tmp > 0:
#             n = tmp // pow(10, dig_level)
#             first = n
#             if dig_level == 3:
#                 while n > 0:
#                     result += dct[1000]
#                     n -= 1
#             elif dig_level == 2:
#                 if n > 0 and n < 4:
#                     while n > 0:
#                         result += dct[100]
#                         n -= 1
#                 elif n == 4:
#                     result += dct[400]
#                 elif n == 5:
#                     result += dct[500]
#                 elif n > 5 and n < 9:
#                     result += dct[500]
#                     while n > 5:
#                         result += dct[100]
#                         n -= 1
#                 else:
#                     result += dct[900]
#             elif dig_level == 1:
#                 if n > 0 and n < 4:
#                     while n > 0:
#                         result += dct[10]
#                         n -= 1
#                 elif n == 4:
#                     result += dct[40]
#                 elif n == 5:
#                     result += dct[50]
#                 elif n > 5 and n < 9:
#                     result += dct[50]
#                     while n > 5:
#                         result += dct[10]
#                         n -= 1
#                 else:
#                     result += dct[90]
#             else:
#                 if n > 0 and n < 4:
#                     while n > 0:
#                         result += dct[1]
#                         n -= 1
#                 elif n == 4:
#                     result += dct[4]
#                 elif n == 5:
#                     result += dct[5]
#                 elif n > 5 and n < 9:
#                     result += dct[5]
#                     while n > 5:
#                         result += dct[1]
#                         n -= 1
#                 else:
#                     result += dct[9]
#             tmp -= first * pow(10, dig_level)
#             if tmp // pow(10, dig_level) <= 0:
#                 while tmp // pow(10, dig_level) <= 0:
#                     if dig_level < 0:
#                         break
#                     dig_level -= 1
#             else:
#                 dig_level -= 1
#         return result
class Solution:
    def intToRoman(self, num: int) -> str:
        lookup = {
            1:'I',
            4:'IV',
            5:'V',
            9:'IX',
            10:'X',
            40:'XL',
            50:'L',
            90:'XC',
            100:'C',
            400:'CD',
            500:'D',
            900:'CM',
            1000:'M'     
        }
        res = ""
        # pdb.set_trace()
        for key in sorted(lookup.keys())[::-1]:
            a = num // key
            if a == 0:
                continue
            res += (lookup[key] * a)
            num -= a * key
            if num == 0:
                break
        return res

# if __name__ == '__main__':
#     s = Solution()
#     a = input('enter albic num: ')
#     print(s.intToRoman(int(a)))
